using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
using System.Reflection;

namespace DacTaHinhThuc
{
    class TrangThai
    {
        #region fields
        private string m_ten;
        private bool m_status;
        private bool m_IsStart;
        private bool m_IsEnd;
        #endregion

        #region properties
        public bool IsEnd
        {
            get { return this.m_IsEnd; ;}
            set { this.m_IsEnd = value; }
        }
        public bool IsStart
        {
            get { return this.m_IsStart; }
            set { this.m_IsStart = value; }
        }
        public string Ten
        {
            get { return this.m_ten; }
            set { this.m_ten = value; }
        }
        public bool Status
        {
            get { return this.m_status; }
            set { this.m_status = value; }
        }
        #endregion

        #region phuong thuc
        public TrangThai()
        {
            this.m_ten = "";
            this.m_status = false;
            this.m_IsEnd = false;
            this.m_IsStart = false;
        }
        public TrangThai(string ten)
        {
            this.m_ten = ten;
            this.m_status = false;
            this.m_IsEnd = false;
            this.m_IsStart = false;
        }
        #endregion
    }
    class CungTruyen
    {
        #region fields
        private TrangThai m_TtStart;
        private TrangThai m_TtEnd;
        private string m_sValue;
        private bool m_bIsActive;
        #endregion

        #region properties
        public bool IsActive
        {
            get { return this.m_bIsActive; }
            set { this.m_bIsActive = value; }
        }
        public TrangThai TtStart
        {
            get { return this.m_TtStart; }
            set { this.m_TtStart = value; }
        }
        public TrangThai TtEnd
        {
            get { return this.m_TtEnd; }
            set { this.m_TtEnd = value; }
        }
        public string Value
        {
            get { return this.m_sValue; }
            set { this.m_sValue = value; }
        }
        #endregion

        #region phuong thuc
        public CungTruyen()
        {
            this.m_TtEnd = this.m_TtStart = null;
            this.m_sValue = "";
            ///////////////
            this.m_bIsActive = true;
        }

        public CungTruyen(TrangThai start, TrangThai end, string value)
        {
            this.m_TtStart = start;
            this.m_TtEnd = end;
            this.m_sValue = value;
            ////////////
            this.m_bIsActive = true;

        }

        /// <summary>
        /// kiem tra xem cung truyen do co phai la 1 vong khuyen hay khong
        /// </summary>
        /// <returns>
        /// true: la vong khuyen
        /// false: khong phai la vong khuyen
        /// </returns>
        public bool IsCircle()
        {
            if (this.TtStart.Ten == this.TtEnd.Ten)
            {
                return true;
            }
            return false;
        }

        /// <summary>
        /// kiem tra xem cung truyen co dang nhan active hay khong
        /// </summary>
        /// <returns>
        /// true: cung dang active
        /// false: cung khong active
        /// </returns>
        public bool CheckActive()
        {
            if (this.m_TtStart.Status)
            {
                this.m_bIsActive = true;
                return true;
            }
            else
            {
                this.m_bIsActive = false;
                return false;
            }
        }
        public bool CompareValue(char s)
        {
            switch (this.m_sValue)
            {
                case "digit":
                    if (s >= '0' && s <= '9')
                    {
                        return true;
                    }
                    break;
                case "char":
                    if ((s >= 'a' && s <= 'z') || (s >= 'A' && s <= 'Z') || s == '_')
                    {
                        return true;
                    }
                    break;
                case "all":
                    if ((s >= 'a' && s <= 'z') || (s >= 'A' && s <= 'Z') || s == '_' || (s >= '0' && s <= '9'))
                    {
                        return true;
                    }
                    break;
            }
            return false;
        }

        #endregion
    }
    class DFA
    {
        #region fields
        private CungTruyen[] listCung;
        private TrangThai[] listTT;
        private TrangThai m_nextState;
        #endregion

        #region methods

        public DFA()
        {
            this.Input();
        }

        private CungTruyen[] FindCungStart()
        {
            int i;
            List<CungTruyen> list = new List<CungTruyen>();

            for (i = 0; i < this.listCung.Length; i++)
            {
                if (this.listCung[i].TtStart.IsStart)
                {
                    list.Add(this.listCung[i]);
                }
            }
            return list.ToArray();
        }

        public bool CheckString(string m_sTestStr)
        {
            int j;
            int i;

            //kiem tra chuoi rong
            if (m_sTestStr == null)
                return false;

            //di tu trang thai dau tien
            CungTruyen[] CungStart = this.FindCungStart();
            if (CungStart.Length == 0)
            {
                return false;
            }
            //kiem tra cung truyen dau tien truoc voi ky tu dau tien cua chuoi nhap
            for (i = 0; i < CungStart.Length; i++)
            {
                if (CungStart[i].CompareValue(m_sTestStr[0]))
                {
                    if (!CungStart[i].IsCircle())
                    {
                        CungStart[i].TtStart.Status = false;
                        CungStart[i].TtEnd.Status = true;
                    }
                    else
                    {
                        CungStart[i].TtEnd.Status = true;
                    }
                    ////////////////////////////
                    this.m_nextState = CungStart[i].TtEnd;
                    break;
                }
            }

            if (this.m_nextState == null)
            {
                return false;
            }

            //kiem tra cac ky tu con lai
            for (i = 1; i < m_sTestStr.Length; i++)
            {
                CungTruyen[] arr = this.TimCungTruyen(m_sTestStr[i], this.m_nextState);
                if (arr.Length == 0)
                {
                    return false;
                }
                else
                {
                    for (j = 0; j < arr.Length; j++)
                    {
                        if (arr[j].CompareValue(m_sTestStr[i]))
                        {
                            if (!arr[j].IsCircle())
                            {
                                arr[j].TtEnd.Status = true;
                                arr[j].TtStart.Status = false;
                            }
                            else
                            {
                                arr[j].TtEnd.Status = true;
                            }
                            this.DisableAllTrangThaiExcept(arr[j].TtEnd);
                            this.m_nextState = arr[j].TtEnd;
                            if (this.m_nextState == null)
                            {
                                return false;
                            }
                            break;
                        }
                    }
                }
            }
            return CheckAccept();
        }
        private CungTruyen[] TimCungTruyen(char value, TrangThai t)
        {
            int i;
            List<CungTruyen> list = new List<CungTruyen>();

            for (i = 0; i < this.listCung.Length; i++)
            {
                if (this.listCung[i].TtStart.Ten == t.Ten && this.listCung[i].CompareValue(value))
                {
                    list.Add(this.listCung[i]);
                }
            }
            return list.ToArray();
        }
        private void DisableAllTrangThaiExcept(TrangThai tt)
        {
            int i;
            for (i = 0; i < this.listTT.Length; i++)
            {
                if (this.listTT[i] != tt)
                {
                    this.listTT[i].Status = false;
                }
            }
        }

        private bool CheckAccept()
        {
            int i;
            for (i = 0; i < this.listCung.Length; i++)
            {
                if (this.listCung[i].TtEnd.IsEnd && this.listCung[i].TtEnd.Status)
                {
                    this.listCung[i].TtEnd.Status = false;
                    return true;
                }
            }
            return false;
        }

        private void Input()
        {
            try
            {
                string[] arr = { " " };
                int i;
<<<<<<< .mine
                                
                string startup = Form1.m_startUp + "\\DFA.txt";                
                
                StreamReader sr = new StreamReader(startup);
                
=======
                
                string startup = Path.GetDirectoryName(Assembly.GetExecutingAssembly().GetName().CodeBase);
                startup += "\\DFA.txt";
                startup = startup.Substring(6);
                
                StreamReader sr = new StreamReader(startup);

>>>>>>> .r17
                
                //doc vao so trang thai va so cung truyen
                string tmp = sr.ReadLine();

                string[] listStr = tmp.Split(arr, StringSplitOptions.RemoveEmptyEntries);
                int n;
                int m;

                n = int.Parse(listStr[0]);
                m = int.Parse(listStr[1]);

                this.listTT = new TrangThai[n];
                this.listCung = new CungTruyen[m];

                //khoi tao danh sach cac trang thai
                for (i = 0; i < n; i++)
                {
                    this.listTT[i] = new TrangThai(i.ToString());
                }

                //doc vao danh sach cac cung truyen
                int iStart;
                int iEnd;
                for (i = 0; i < m; i++)
                {
                    tmp = sr.ReadLine();
                    listStr = tmp.Split(arr, StringSplitOptions.RemoveEmptyEntries);

                    iStart = int.Parse(listStr[0]);
                    iEnd = int.Parse(listStr[1]);

                    this.listCung[i] = new CungTruyen(this.listTT[iStart], this.listTT[iEnd], listStr[2]);

                }

                //doc vao trang thai bat dau va trang thai ket thuc
                tmp = sr.ReadLine();
                listStr = tmp.Split(arr, StringSplitOptions.RemoveEmptyEntries);

                //trang thai bat dau
                iStart = int.Parse(listStr[0]);
                this.listTT[iStart].IsStart = true;
                this.listTT[iStart].Status = true;

                //trang thai ket thuc
                for (i = 1; i < listStr.Length; i++)
                {
                    iEnd = int.Parse(listStr[i]);
                    this.listTT[iEnd].IsEnd = true;
                }

                sr.Close();
            }
            catch (Exception ex)
            {
                throw new Exception(ex.Message);
            }
        }

        #endregion methods
    }
}
